home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 3: CDPD 3 / Almathera Ten on Ten - Disc 3: CDPD3.iso / fish / 001-100 / 001-025 / 004 / bm / makeskip.c < prev    next >
C/C++ Source or Header  |  1995-03-17  |  1KB  |  46 lines
  1. #include "bm.h"
  2. extern char *malloc();
  3.  
  4. MakeSkip(Pattern,Skip1,Skip2,PatLen)
  5. char Pattern[];
  6. int Skip1[], Skip2[];
  7. int PatLen;
  8. /* generate the skip tables for Boyer-Moore string search algorithm.
  9. * Skip1 is the skip depending on the character which failed to match
  10. * the pattern, and Skip2 is the skip depending on how far we got into
  11. * the pattern. Pattern is the search pattern and PatLen is strlen(Pattern) */
  12. {
  13.     int *BackTrack; /* backtracking table for t when building skip2 */
  14.     int c; /* general purpose constant */
  15.     int j,k,t,tp; /* indices into Skip's and BackTrack */
  16.  
  17.     if (!(BackTrack = (int *) malloc(PatLen * (sizeof (int))))){
  18.         fprintf("bm: can't allocate space\n");
  19.         exit(2);
  20.     } /* if */
  21.     for (c=0; c<=MAXCHAR; ++c)
  22.         Skip1[c] = PatLen;
  23.     for (k=0;k<PatLen;k++) {
  24.         Skip1[Pattern[k]] = PatLen - k - 1;
  25.         Skip2[k] = 2 * PatLen - k - 1;
  26.     } /* for */
  27.     for (j=PatLen - 1,t=PatLen;j >= 0; --j,--t) {
  28.         BackTrack[j] = t;
  29.         while (t<PatLen && Pattern[j] != Pattern[t]) {
  30.             Skip2[t] = min(Skip2[t], PatLen - j - 1);
  31.             t = BackTrack[t];
  32.         } /* while */
  33.     } /* for */
  34.     for (k=0;k<=t;++k)
  35.         Skip2[k] = min(Skip2[k],PatLen+t-k);
  36.     tp=BackTrack[t];
  37.     while(tp<PatLen) {
  38.         while(t<PatLen) {
  39.             Skip2[t] = min(Skip2[t],tp-t+PatLen);
  40.             ++t;
  41.         } /* while */
  42.         tp = BackTrack[tp];
  43.     } /* while */
  44.     free(BackTrack);
  45. } /* MakeSkip */
  46.